index.md (2753B)
1 +++ 2 title = 'Partial orders' 3 +++ 4 # Partial orders 5 partial order on V: relation R of type V × V. satisfies reflexivity, anti-symmetry, transitivity 6 7 example: relation ≤ is partial order on N 8 9 - ∀n: n ≤ n (reflexivity) 10 - ∀m, n: m≤n ∧ n≤m ➝ m = n (anti-symmetry) 11 - ∀k, m, n: k≤m ∧ m≤n ➝ k≤n (transitivity) 12 13 example: the relation ⊆ is partial order on P(V) 14 15 - ∀A: A ⊆ A (reflexivity) 16 - ∀A,B: A ⊆ B ∧ A ➝ A = B (anti-symmetry) 17 - ∀A,B,C: A ⊆ B ∧ B ⊆ C ➝ A ⊆ C (transitivity) 18 19 ## linear ordering relations 20 partial order R on set V, then: 21 22 - x, y ∈ V are _comparable_ if x R y or y R x 23 - R is _linear/total order_ if all x,y ∈ V are comparable 24 25 e.g. relation ≤ on N: for all n,m in N — n ≤ m or m ≤ n — _total_ 26 27 e.g. relation ⊆ on P({1,2}): {1} is not a subset of {2}, {2} is not a subset of {1} — _not total_ 28 29 ## strict partial ordering relations 30 31 if partial order R on set V, then strict partial order S corresponding to R is defined by 32 33 x S y ⟷ x R y and x ≠ y 34 35 a strict partial order is irreflexive, anti-symmetric, transitive 36 37 ## Hasse diagrams 38 apparently a partial ordering relation is complicated as fuck: 39 40  41 42 so get rid of some arrows and make a Hasse diagram — omit reflexivity and transitivity 43 44 the arrows create chains that split and merge, elements in the same chain are comparable 45 46  47 48 Algorithm: 49 1. For all x ∈ V — Gx := {y : y ≠ x and x R y} 50 2. For all x ∈ V — Hx := Gx \ {z : z ∈ Gy for a y ∈ Gx} 51 3. For all x ∈ V — draw and arrow from x to every y ∈ Hx 52 53 example: 54  55 56 ## Cartesian order on A × B 57 \<a1, b1\> ≤ \<a2, b2\> ⟷ a1 ≤A a2 and b1 ≤B b2 58 59 ordered by points, if both are smaller 60 61 cartesian order on A × B is a partial order 62 63  64 65 ## Lexicographic order on A × B 66 \<a1, b1\> ≤ \<a2, b2\> ⟷ (a1 \<A a2) ∨ (a1 = a2 ∧ b1 ≤B b2) 67 68 like in a dictionary 69 70 lexicographic order on A× B is a partial order, total if ≤A on A and ≤B on B are total 71 72  73 74 ## Minimal and maximal elements 75 (V, ≤) is a partially ordered set, A ⊆ V, m ∈ A 76 77 m is: 78 79 - largest element of A — if ∀a ∈ A : a ≤ m 80 - smallest element of A — if ∀a ∈ A : m ≤ a 81 - maximal element of A — if ∀a ∈ A : (M ≤ a ➝ m = a) — no outgoing arrows on Hasse diagram 82 - minimal element of A — if ∀a ∈ A : (a ≤ m ➝ a = m) — no incoming arrows on Hasse diagram 83 84 Every maximum of A is a maximal element of A. 85 If A has a maximum, it is the only maximal element.